package labuladong.开篇;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 动态规划
public class 硬币兑换 {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        System.out.println(dp(new int[]{1, 2, 5}, 11));
        System.out.println(dp2(new int[]{1, 2, 5}, 11, map));
        System.out.println(dp3(new int[]{1, 2, 5}, 11));
    }

    public static int dp(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int res = Integer.MAX_VALUE;
        for(int i=0; i<coins.length; i++) {
            int subRes = dp(coins, amount-coins[i]);
            if (subRes == -1) continue;
            res = Math.min(res, 1+subRes);
        }
        if (res != Integer.MAX_VALUE) return res;
        return -1;
    }

    public static int dp2(int[] coins, int amount, Map<Integer, Integer> map) {
        if (map.containsKey(amount)) return map.get(amount);
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int res = Integer.MAX_VALUE;
        for(int i=0; i<coins.length; i++) {
            int subRes = dp2(coins, amount-coins[i], map);
            if (subRes == -1) continue;
            res = Math.min(res, 1+subRes);
        }
        if (res != Integer.MAX_VALUE)
            map.put(amount, res);
        else
            map.put(amount, -1);
        return map.get(amount);
    }

    public static int dp3(int[] coins, int amount) {
        int[] dict = new int[amount+1];
        Arrays.fill(dict, amount+1);
        dict[0] = 0;
        for (int i=0; i<amount+1; i++) {
            for(int coin : coins) {
                if (i-coin < 0) continue;
                dict[i] = Math.min(dict[i], 1+dict[i-coin]);
            }
        }
        return (dict[amount] == amount+1) ? -1 : dict[amount];
    }
}
